//深度优先
//需要一个数组检验一个点是否已经访问过了，还有一个数组edgeTo，用于得到路径，里面的内容是对于一个正在访问的点，是从哪个点过来的
//同时还能通过edgeto函数得到路径
//递归访问未被访问点
//与和s相连的边的边数成正比
import edu.princeton.cs.algs4.*;
public class Path {
    boolean marked[];
    int edgeTo[];   
    int s;           //起点
    //在图g中以s为起点
    public Path(Graph g,int s)
    {
        marked=new boolean[g.V()];
        edgeTo=new int[g.E()];
        this.s=s;
        Dfs(g,s);
    }

    public void Dfs(Graph g,int v)
    {
        marked[v]=true;
        for(int i:g.adj(v))
        {
           if(!marked[i])
           {
            marked[i]=true;
            Dfs(g,i);
            edgeTo[i]=v;
           }
        }
    }
     
    //有没有从s到v的路径
    public boolean HasPathTo(int v)
    {
        return marked[v];
    }

    //从v到s的路径
    Iterable<Integer> PathTo(int v)
    {
        if(!HasPathTo(v))
        {
            return null;
        }
        Stack<Integer> path=new Stack<Integer>();
        for(int i=v;i!=s;i=edgeTo[i])
        {
            path.push(i);
        }
        path.push(s);
        return path;
    }
}
